Word ladder II

Time: O(NxD); Space: O(D); hard

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: 1. Only one letter can be changed at a time 2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Notes:

  • Return an empty list if there is no such transformation sequence.

  • All words have the same length.

  • All words contain only lowercase alphabetic characters.

  • You may assume no duplicates in the word list.

  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

Output:

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Explanation * “hit”->“hot”->“dot”->“dog”->“cog” * “hit”->“hot”->“lot”->“log”->“cog” * The dictionary order of the first sequence is less than that of the second.

Example 2:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

Output: []

Explanation:

  • The endWord “cog” is not in wordList, therefore no possible transformation

[1]:

from collections import defaultdict
from string import ascii_lowercase
class Solution1(object):
    """
    Time: O(N*D), N is length of string, D is size of dictionary
    Space: O(D)
    """
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        dictionary = set(wordList)
        result, cur, visited, found, trace = [], [beginWord], set([beginWord]), False, defaultdict(list)

        while cur and not found:
            for word in cur:
                visited.add(word)

            next = set()
            for word in cur:
                for i in range(len(word)):
                    for c in ascii_lowercase:
                        candidate = word[:i] + c + word[i + 1:]
                        if candidate not in visited and candidate in dictionary:
                            if candidate == endWord:
                                found = True
                            next.add(candidate)
                            trace[candidate].append(word)
            cur = next

        if found:
            self.backtrack(result, trace, [], endWord)

        return result

    def backtrack(self, result, trace, path, word):
        if not trace[word]:
            result.append([word] + path)
        else:
            for prev in trace[word]:
                self.backtrack(result, trace, [word] + path, prev)

[3]:

s = Solution1()

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
assert s.findLadders(beginWord, endWord, wordList) == [
  ["hit","hot","lot","log","cog"],
  ["hit","hot","dot","dog","cog"]
]

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
assert s.findLadders(beginWord, endWord, wordList) == []